1. Field of the Invention
The invention relates to navigation systems and, in particular, to methods and systems for determining routes in a road network on navigation systems.
2. Related Art
Typical navigation systems provide a feature of determining a route between a given starting point to a given destination. This feature may be particularly useful in car, or other mobile, navigation systems particularly when the route information is determined to result in an optimum route. As used in this specification, the term “optimum route” includes a least-cost route, the costs of a route being determined by the sum of costs of road segments traversed when travelling on the route plus the sum of costs associated with junctions or road segment vertices. Several different cost models may be employed in navigation systems, e.g., a shortest-route model in which the costs of a road segment are given by the length of the road segment, or a fastest-route model in which the costs of a road segment are given by the length of the road segment divided by a characteristic travel speed on the road segment. Further, cost models may also take into account user preferences, such as avoiding highways, avoiding tunnels, or avoiding ferry connections.
Several algorithms for finding an optimum route are known in the art. Some known optimum route algorithms include the Dijkstra's algorithm and the A*-algorithm. In Dijkstra's algorithm, the road network, or more generally, a graph representing the road network is analyzed starting from the starting point of the route by edge relaxation. The different vertices in the road network are visited in order of minimum costs associated with a route connecting the vertex and the starting point. When the destination is expanded, an optimum route from the starting point to the destination has been found, and Dijkstra's algorithm terminates.
The A*-algorithm is a modification of Dijkstra's algorithm, which employs an estimation function for all vertices of the road network. The estimation function for a given vertex provides estimates costs associated with an optimum route connecting a given vertex and the destination. In a route search, different paths are ranked according to a priority, which may be determined by a sum of the costs accrued from the starting point to the vertex so far, and the estimation function of the vertex. If the estimation function is such that it may not overestimate costs of an optimum route connecting a vertex and the destination, the A*-algorithm may find a correct solution to the optimum path problem.
For an optimum route search on a road network, a heuristic estimation may be employed. Such a heuristic estimation may be determined based on an air-line distance between the vertex and the destination in a shortest-route search. The air-line distance may be divided by a characteristic travel speed in a fastest-route search. Typically, the better the estimation function, the smaller the number of road segment vertices that are visited in determining the optimum route and the shorter the algorithm run time.
However, estimation functions based on an air-line distance may be imprecise. Further, in navigation systems on-board a vehicle, memory and run time restrictions may be limited. Because of such limitations, it may be feasible to directly apply Dijkstra's algorithm and the A*-algorithm as may be commonly used in Europe or the US in view of the number of road segments and road segment vertices in these road networks. Dijkstra's algorithm or the A*-algorithm may often be modified for use in a navigation system, for example, by providing a classification of different road segments into different layers or by providing additional information characterizing a road network geometry, which may be determined offline and facilitate an optimum route search in the navigation system.
In this context, a least-cost routing system may use a reach metric that quantifies the relevance of a road segment for long distance travel. This reach metric may be advantageously based on map geometry only. However, there is a disadvantage of the reach metric being highly non-local in the sense that the reach of a given road segment may depend on the costs associated with a different road segment that may be far away. For example, an increase in cost factor of a road segment may result in an increase or a decrease in the reach of a different road segment, even if it is far away.
It would be desirable to use improved navigation systems and, in particular, to use methods and systems for determining routes in a road network on navigation systems.